package com.vint.lintcode;

import com.vint.common.ListNode;

/**
 * 求两个链表的交叉点
 */
public class Lintcode380 {
	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		if (null == headA || null == headB) {
			return null;
		}

		if (headA == headB) {
			return headA;
		}

		if (getTailNode(headA) != getTailNode(headB)) {
			return null;
		}

		ListNode tailA = getTailNode(headA);
		tailA.next = headA;

		return detectCycle(headB);
	}

	public ListNode getTailNode(ListNode head) {
		if (null == head || null == head.next) {
			return head;
		}
		ListNode tail = head;
		while (null != tail.next) {
			tail = tail.next;
		}
		return tail;
	}
	public ListNode detectCycle(ListNode head) {
		ListNode first = head;
		ListNode meetNode = hasCycle(first);
		if (null == meetNode) {
			return null;
		}
		ListNode second = head;
		first = meetNode;
		while(second != first) {
			first = first.next;
			second = second.next;
		}
		return second;
	}

	public ListNode hasCycle(ListNode head) {
		if (null == head) {
			return head;
		}
		ListNode first = head;
		if (head.next == head) {
			return head;
		}
		if (null == head.next) {
			return null;
		}
		first = head.next;
		ListNode two = head.next.next;
		while(null != first && null != two) {
			if (first == two) {
				return first;
			}
			first = first.next;
			if (null == two.next) {
				return null;
			}
			two = two.next.next;
		}
		return null;
	}
	public static void main(String[] args) {
	}
}
